The availability of broadband communication channels to end-user devices has enabled ubiquitous media coverage with image, audio, and video content. The increasing amount of multimedia content that is transmitted globally has boosted the need for intelligent content management. Providers must organize their content and be able to detect unauthorized broadcast, usage, and alteration. Similarly, broadcasters and market researchers want to know when and where specific footage has been broadcast. Content monitoring, market trend analysis, and copyright protection are emerging applications in the new world of digital media.
Content-based retrieval (CBR) systems are commonly used to access, organize, and analyze information stored in the form of digital data representations. The digital data representations can be searched or otherwise queried to determine matches to an existing, target set of digital data representations. Matches can be determined by the degree of similarity between the queried digital data representations and the existing set of digital data representations. It is common for these digital data representations to be classified as follows: digital text, digital graphics, digital images, digital audio, digital video, digital audio and video, and combinations thereof.
Each digital data representation class, generally shares attributes, or features, particular to its class. A feature model can used to identify and define features specific to a class, and represent each digital data representation in a class by a feature set in a feature space of the given class. Consequently, a query can be confined to matching a feature set of the queried digital data representation to a feature set of the existing set of digital data representations, where both queried and existing digital data representation features are in the same feature space.
Matching features automatically, generally requires that features first be reduced to a set of numerical values. This can be accomplished using feature data sets and feature metrics that can be used for matching according to one or more rules referred to as feature measures. Feature measures are commonly determined by distances measured between corresponding feature data set elements in features of the queried and target digital data representations feature space. Such distance measures in a K-dimensional feature space are commonly referred to as K-dimensional, Nearest-Neighbor queries, or K-NN queries.
In the mid-1970s, hierarchical structures, such as tree structures, were introduced to index K-NN queries. In 1984, Guttman proposed an R-tree indexing structure, which was followed by an R+-tree variant in 1987 by Sellis, and a dynamic R*-tree variant in 1990 by Beckman. Features were defined in the leaf structure, partitions of the feature space, in each of the aforementioned tree structures. Distances were found to irregular convex subspaces spanning the partitions. The irregular convex subspaces made indexed K-NN queries in each of the aforementioned tree structures nearly intractable in feature spaces with dimension K greater than approximately 20 and with low distance measure variance.
Principle component analysis approaches, implemented in 1995 by Faloutsos and 1996 by Ng and Sedighain, reduced feature space dimensions using a fast approximation of the Karhunen-Loeve Transform. However, results consistently showed a loss in accuracy in K-NN queries with significant reduction in feature space dimension.
Relational databases in feature space eliminated the tree structure topology, allowing metric spaces to be defined to span the tree-structure topology with no intrinsic information of the topology itself. In 1999, Vleugels implemented a metric space and a metric space to a d-dimensioned vantage-space transform to produce a feature measure for K-NN queries, but lost queried accuracy in the transformation from relational databases to tree-structure databases.
A second set of relational database approaches were implemented by Chiueh in 1994 and by Ciaccia in 1997. The Chiueh vantage-point tree and Ciaccia M-tree both partitioned feature space recursively into smaller and smaller feature subspaces, each defined by regular hyperspheres. Centroids of hyperspheres are searched in K-NN queries, reducing complexity.
K-NN queries using the aforementioned tree structures, relational database structures, and combinations of the tree and relational database structures do not take advantage of feature set orthogonality inherent in feature sets of many digital data representations. Clusters of features can be partitioned in feature space recursively into smaller and smaller disjoint feature subspaces, nested disjoint feature subspaces, each defined by regular hyperspheres, by iteratively clustering features according to the inherent nature of the defined feature sets.
K-NN queries involving feature subspaces comprising disjoint hyperspheres allow for partial searches and increase queried accuracy for reduced search times.